class Solution {
public:
    // 时间复杂度 O(N)
    // 空间复杂度 O(1)
    /*
    int GetNumberOfK(vector<int> data ,int k) {
       int len = data.size();
        int ans = 0;
        for(auto& t : data) {
            if(k == t) ans++;
            if(t > k) break;
        }
        return ans;
    }
    */
    // 二分搜索，时间复杂度O(logN),空间复杂度O(1)
    int GetNumberOfK(vector<int> data ,int k) {
        int len = data.size();
        int l = 0, r = len;
        int pos1,pos2,mid;
        if(len == 0) return 0;
        while(l < r) {
            mid = l + (r - l)/2;
            if(data[mid] < k) {
                l = mid + 1;
            }
            else if(data[mid] > k) {
                r = mid;
            }
            else {
                r = mid;
            }
        }
        if(data[l] == k) {
            pos1 = l;
            l = 0;
            r = len;
        }
        else
            return 0;
        while(l < r) {
            mid = l + (r - l)/2;
            if(data[mid] < k) {
                l = mid + 1;
            }
            else if(data[mid] > k) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        if(data[r-1] == k) {pos2 = l-1;}
            return pos2 - pos1 + 1;
    }
    
};